function quickSort(arr, L, R) {
  if (L >= R) {
    return
  }
  // 用于取随机值(实际感觉并没什么暖用,概率问题)
  // swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R)
  let [left, right] = partition(arr, L, R)
  quickSort(arr, L, left - 1)
  quickSort(arr, right + 1, R)
}

function swap(arr, L, R) {
  ;[arr[L], arr[R]] = [arr[R], arr[L]]
}

/*  */
// 分区
function partition(arr, L, R) {
  let left = L - 1
  let right = R + 1
  let num = arr[R]
  // 核心操作,很强
  while (L < right) {
    if (arr[L] < num) {
      swap(arr, ++left, L++)
    } else if (arr[L] > num) {
      swap(arr, L, --right)
    } else {
      L++
    }
  }
  // swap(arr, R, right)

  return [left + 1, right]
}
let arr = [1, 7, 3, 2, 5, 5]
quickSort(arr, 0, arr.length - 1)
// getPosition(arr, 0, arr.length - 1)
console.log(arr)
